package com.lims.algorithm.algset.linked;

import java.util.ArrayList;
import java.util.Stack;
import java.util.function.Consumer;
/**
 * <功能简述>单链表反转
 *
 * @author: lims
 * @create: 2019-04-19 10:26
 */
public class SingleLink {
    static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

    /***********************单链表反转***********************/
    /**
     * 反转，递归法
     *
     * @param node
     * @return
     */
    public static Node reverseRecur(Node node) {
        if (node == null || node.next == null) {
            return node;
        } else {
            Node nn = reverseRecur(node.next);
            //下一个节点的指针指向上一个节点
            node.next.next = node;
            //断掉当前节点指向下一节点的指针
            node.next = null;
            return nn;
        }
    }

    /**
     * 反转，移动指针法
     *
     * @param node
     * @return
     */
    public static Node reverseMovePoint(Node node) {
        //前一个节点指针
        Node pre = null;
        //当前节点指针
        Node cur = node;
        while (cur != null) {
            //当前节点的下一个节点
            Node nextNode = cur.next;
            //当前节点指向下一个节点的指针反转，指向前一个节点
            cur.next = pre;
            //当前节点变前一个(pre)节点，前一个节点的指针指向当前节点
            pre = cur;
            //下一个节点变当前(cur)节点，当前节点指针指向下一个节点
            cur = nextNode;
        }
        return pre;
    }

    /**********************倒着打印链表************************/
    /**
     * 递归倒着打印
     *
     * @param node
     */
    public static void printTailRec(Node node) {
        if (node.next == null) {
            System.out.print(node.value + " ");
            return;
        } else {
            printTailRec(node.next);
        }
        System.out.print(node.value + " ");
    }

    /**
     * 遍历，用栈存储，倒着打印
     *
     * @param node
     */
    public static void printTailStack(Node node) {
        Stack<Node> stack = new Stack<Node>();
        if (node == null) {
            System.out.println("已经为null");
            return;
        } else {
            while (node != null) {
                stack.push(node);
                node = node.next;
            }
            while (!stack.isEmpty()) {
                System.out.print(stack.pop().value + " ");
            }
        }
    }

    /**
     * 打印单链表
     * @param head
     */
    public static void printLinked(Node head) {
        Node tmp = head;
        while (true) {
            System.out.print(tmp.value + " ");
            if (tmp.next == null)
                break;
            else
                tmp = tmp.next;
        }
    }

    public static ArrayList<Integer> printListFromTailToHead(Node listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.value);
            listNode = listNode.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add(stack.pop());
        }
        return list;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        System.out.println("反转前打印==");
        printLinked(node1);
        System.out.println("");

        ArrayList list = printListFromTailToHead(node1);
        list.forEach(new Consumer() {
            @Override
            public void accept(Object o) {
                System.out.print(o + " ");
            }
        });

        /*************************/

        Node nodea = new Node(1);
        Node nodeb = new Node(2);
        Node nodec = new Node(3);
        Node noded = new Node(4);
        nodea.next = nodeb;
        nodeb.next = nodec;
        nodec.next = noded;

        System.out.println("反转前打印==");
        //while (true)
        SingleLink.printLinked(nodea);
        System.out.println("==反转==");
        Node n = reverseRecur(nodea);
        System.out.println("==反转后打印==");
        SingleLink.printLinked(n);

        System.out.println("==第二次反转==");
        Node nn = reverseMovePoint(n);
        System.out.println("==第二次反转后打印==");
        printLinked(nn);
    }
}
